Bit manipulation is the process of altering or manipulating bits in memory, and typically consists of the following activities: clearing bits, testing bits, comparing bits, inverting bits, inserting bits into a bit string and extracting bits from a bit string. From some of the earliest microprocessor days, AND, OR, EOR, NOT, TEST and SHIFT and ROTATE instructions were primarily relied upon to manipulate bits of data.
In conventional systems, a general purpose computer may spend a significant portion of available processing resources in order to handle variable length data streams in coding and decoding algorithms. The computer loads the variable length bitstream directly from memory (which acts as a bitstream buffer) into a register and then performs various procedures on the data, such as deleting bits, getting bits and showing bits. Interactions between the register and the memory can require a significant number of operations, depending upon the size of the register. For example, performing a “show_bits” function, denoted only herein as the name “show_bits” for ease of understanding its function, which functions to locate the bits of interest in proper alignment in a register using a conventional 32-bit register can require a significant number of operations (e.g., eight operations) if the data of interest does not exceed 32 bits and does not cross a 32-bit boundary in the memory, or even more operations (e.g., 13 operations) if the data of interest does cross the 32-bit boundary. Of course, the number of instructions and the bit boundary may change depending on the instruction set architecture of the processor.
For instance, FIG. 1 illustrates a diagram of a conventional method of showing N bits (“Show_Bits(N)”). Show_Bits(N) provides an integer number, N, of bits in a register. For instance, bitstream data is loaded into memory, such as system memory, and the Show_Bits(N) method places or loads a predetermined number of bitstream bits, N, in a register. Each register and memory location may be addressed with a 32 bit address and two conditions must be accounted for with the Show_bits command: the case where the N bits requested cross a 32-bit boundary in system memory and the case where the N bits requested do not cross a 32-bit boundary in system memory. The bit size of the actual memory locations can vary and can be addressed virtually. In general, a register is distinguished from system memory in that a register is memory which has a specific address which is used to hold information of a specific kind. The bitstream pointer points to a specific memory address in which bitstream data is stored. The bitstream data can arrive asynchronously and can be of variable length.
For example, it may be desired to show a byte of memory from the 70th through the 77th bit locations, a 32-bit boundary occurs at the 95th and 63rd bit (starting bit position occupying the 0th bit position). This represents an instance where N bits does not cross the 32-bit boundary. In a conventional Show_bits method, after determining that the N bits does not cross the 32 bit boundary, the contents of the memory location addressed by the bitstream pointer containing the N bits is loaded into a 32-bit register. M represents the number of bits from the Nth bit to the next memory address boundary. For the case where the byte of memory represented by the 70th through 77th bit locations is desired to be shown, M is 18, the difference from the next boundary, the 95th bit location to the Nth bit or rather 77th bit. Next, the contents of the 32-bit register is logically left shifted by M bits. This ensures that that portion of the register containing the most significant bits are occupied by the N bits to be shown. For this example, N is 8. This is followed by a logical right shift of the contents of the 32 bit register by 32−N bits, or rather 24 bits for this example. All but the relevant N bit portion of the bitstream now remains in the 32 bit register, right-aligned with all non-relevant bitstream data having been shifted out of the 32-bit register. This conventional Show_Bits method thus typically requires at least 8 operations: 3 arithmetic (M+N, the bit difference between the bit position of the most significant bit position of the bitstream and the 32-bit boundary, and 32−N); 1 compare (with 32); 2 shift; 1 load; and 1 branch to the appropriate Show_Bits(N) routine (based off of the results of the compare).
FIG. 2 is a diagram which illustrates another conventional method of a Show_Bits(N) method where the N bits of bitstream data to be shown crosses a 32-bit boundary in memory and/or is greater than 32 bits. Should, for instance, it be desired to show a byte of memory from the 90th through the 97th bit locations, a 32-bit boundaries occur at the 127th, 95th and 63rd bit (starting bit position occupying the 0th bit position). This represents an instance where N bits crosses a 32-bit boundary. The conventional method loads the desired N bits, which, in this example, occupy two memory locations, into to 32-bit registers. That portion of the N bits which lies in the register with the most significant bit portion is logically shifted to the left by M bits. M being the number of bit positions to the 32-bit boundary of the next memory location. In this instance, M is 30, the difference between the boundary at bit position 127 and the most significant bit position in the N bit portion at bit position 97. That portion of the N bits which lies in the register with the least significant bit portion is logically right shifted by 64−M−N bits. Next, the register with the most significant bit portion of the N bits is logically right shifted by 32−N bits and the resultant registers are logically summed, such as performing a logical OR operation. The resultant value, stored in one of the registers holds the bits desired to be shown. This procedure requires at least 13 operations: 5 arithmetic (M+N, the difference of the Bitstream pointer bit position and the 32-bit boundary, 32−N, 64−M, and (64−M)−N); 1 logical OR; 1 compare with greater than 32; 3 shift; 2 load; and 1 branch to the appropriate Show_Bits(N) routine after determining the compare result.
FIG. 3 is a diagram which illustrates a conventional method of deleting bits (“Delete_Bits(N)”) for deleting N data bits from the bitstream. The bitstream pointer is merely moved forward by N bits. By advancing the bitstream pointer by assigning it a value of the bitstream pointer plus N, those N bits are no longer being addressed. Delete bits requires only one arithmetic operation; namely, bitstream pointer+N.
FIG. 4 is a diagram illustrating a conventional method of getting bits from memory (“Get Bits(N)”, which combines a conventional Delete_Bits(N) with a conventional Show_Bits(N) method. Consequently, N bits will be placed and right-aligned in a 32-bit register and the bitstream pointer will be advanced to the next N address. This operation requires either a minimum of 9 or 14 operations depending upon the Show_Bits(N) operation required.
FIG. 5 is a diagram which illustrates a conventional method to place or store N bits (i.e., “Put_Bits(N)”), in memory such as system memory. Two conditions must be evaluated first; namely, whether the N bit portion to be placed in memory will cross a 32-bit boundary in memory or whether it will not cross a 32-bit boundary in memory. The diagram of FIG. 5 illustrates an example where N bits are desired to be placed at the location pointed to by the bitstream pointer in memory. As shown, M bits exist from the end of a 32-bit boundary in memory to the beginning of the memory location addressed by the bitstream pointer at which the N bits is desired to be stored. For the case where the total of M bits plus N bits is less than or equal to 32, the contents of the memory bound by the 32-bit boundary is loaded into a 32-bit register. This 32-bit register is logically right shifted by 32−M bits, thereby right-aligning the M bits. Next, the M bits are logically left shifted by 32−M bits, thereby left-aligning the M bits. The N bits to be placed into memory are then taken from a right-aligned 32-bit register. The register containing the N bits is then logically left shifted by 32−M−N bits. Next the two 32-bit registers are logically summed (e.g., logically OR'ed) together and the result, including the N bits is stored in memory. This method requires at least 12 operations: namely, 4 arithmetic (such as M+N; the bit difference between the 32 bit boundary and the bitstream pointer); 1 compare; 1 logic OR 3 shift, 1 load, 1 store, and 1 branch to the appropriate Put_Bits routine.
FIG. 6 is a diagram illustrating another conventional Put_Bits(N) method for the case where the N-bit portion does cross the 32-bit boundary on memory. M bits from the 32-bit boundary to the bitstream pointer together with the remaining contents of the 32 bit boundary crossing in memory is loaded into a 32-bit register. The 32-bit register is logically right shifted by 32−M bits. Next, the register contents are logically left shifted by 32−M bits. This serves to left-align the M bit contents with zeros placed in the remaining register bit locations. A register holding the N bits to be placed in memory is logically right shifted by 64−M−N bits. However, the shift is accomplished with yet another register which is loaded with the overflow past a 32-bit boundary. This register is logically right-shifted again by M+N−32 bits. The contents of the register holding the shifted overflow, the register holding the left-shifted M bits and the register originally holding the N bits are logically summed (e.g., logically OR'ed) together and the result is stored in memory. This resulting N bits being placed in memory starting at the memory location pointed to by the bitstream pointer next to the M bits in memory. This requires a minimum of 17 operations: 6 arithmetic (which include calculating the difference between the bitstream pointer location and the 32 bit boundary, 32−M, 64−M, (64−M)−N, M+N and (M+N)−32); 1 compare with greater than 32; 1 logical OR; 3 shifts; 3 loads; 2 stores; and 1 branch to the appropriate Put_Bits(N) routine.
Given the conventional methods of bit manipulation examples of which are described above, there exists a need for improved methods and systems for fast bit manipulation that are more efficient and decrease the number of necessary bit manipulation operations.